#ifndef _CMAP_H_
#define _CMAP_H_

#include <iostream>
#include <vector>
#include <assert.h>
using namespace std;

///顶点

class Graph{
private:
    typedef struct{
        int Weight;
        int initialized;
    }node;
    node*** array;
    int vertexmax = 100;///邻接矩阵的顶点数指针，因为不能使用常数，所以设置为指针
    int undigraph = 0;//有向图0，无向图1；

    ///--------邻接矩阵--------
public:
    Graph(){

    }
    ~Graph(){cout << "Finished" << endl;}
    void MChoice();
    void CreateMGraph();
    void ChangeMWeight();
    void listVertexes();
    void listEdges();

    ///--------邻接表--------
private:
    static int const max = 100;//邻接表的最大节点数
    typedef struct AdjNode{ //邻接点,包含顶点的下标 权重 和指针
        int v;
        int wgt;
        struct AdjNode *next;
    }AdjNode;
    typedef struct VexNode{ //顶点，包含下标 和指向第一个邻接点的指针
        int data;
        AdjNode *first;
    }VexNode;
    typedef struct{// 邻接表里有顶点数以及一个储存顶点的矩阵
        VexNode  Vex[max];
        int vexnum; //顶点数
    }LGraph;
    void _insertedge(LGraph &G, int i, int j, int wgt);
    void _listAdjNode(int data, AdjNode* t);
public:
    LGraph g;
    void LChoice(LGraph &G){
        int choice;
        cout<<"请选择要实现的功能:"<<endl;
        cout<<"给顶点赋权，扣1"<<endl;
        cout<<"罗列当前顶点，扣2"<<endl;
        cout<<"罗列当前顶点和权，扣3"<<endl;
        cout<<"结束程序，扣4"<<endl;

        cin>>choice;
        if(choice==1) {ChangeLWeight(G);LChoice(G);}
        else if(choice==2) {listVertexes(G);LChoice( G);}
        else if(choice==3) {listEdges(G);LChoice(G);}
        else if(choice==4) return;
        else {cout<<"输入有误，请重新输入"<<endl;LChoice(G);};
    }
    void CreateLGraph(LGraph &G);
    ///改变权重
    void ChangeLWeight(LGraph &G){
        int i,j,wgt,times;
        cout<<"输入赋权次数"<<endl;
        cin>>times;
        cout<<"依次输入每条边的两个顶点和权重"<<endl;
        while(times--)
        {
            cin>>i>>j>>wgt;
            i--;j--;
            if((i>=0)&&(i<G.vexnum)&&(j>=0)&&(j<G.vexnum)&&(i!=j)){
                _insertedge(G,i,j,wgt);
                if(undigraph) {_insertedge(G,j,i,wgt);}
                cout<<"本轮完成，还有"<<times<<"次"<<endl;
            }
            else
            {
                cout << "输入顶点信息有误,请重新输入"<<endl;
                times++;//本次输入不算
            }

        }
        cout<<"输入结束"<<endl;
    }
    void listEdges(LGraph G);
    void listVertexes(LGraph G);
};


///--------邻接矩阵--------


void Graph::CreateMGraph() {
    int i,j;
    cout<<"无向图输入1,有向图输入0"<<endl;
    cin>>undigraph;
    cout<<"请输入顶点个数"<<endl;
    cin>>vertexmax;
    array = new node**[vertexmax];
    for(i=0; i<vertexmax; i++){
        array[i]=new node* [vertexmax];
        for(j=0; j<vertexmax; j++){
            array[i][j] = new node;
            array[i][j]->initialized = 0;
        }
    }
    if(undigraph)  cout<<"建立了一个顶点为"<<vertexmax<<"的无向图，使用邻接矩阵存储。"<<endl;
    else cout<<"建立了一个顶点为"<<vertexmax<<"的有向图，使用邻接矩阵存储。"<<endl;
}

void Graph::MChoice() {
    int choice;
    cout<<"请选择要实现的功能:"<<endl;
    cout<<"给顶点赋权，扣1"<<endl;
    cout<<"罗列当前顶点，扣2"<<endl;
    cout<<"罗列当前顶点和权，扣3"<<endl;
    cout<<"结束程序，扣4"<<endl;
    cin>>choice;
    if(choice==1) {ChangeMWeight();MChoice();}
    else if(choice==2) {listVertexes();MChoice();}
    else if(choice==3) {listEdges();MChoice();}
    else if(choice==4) return;
    else {cout<<"输入有误，请重新输入"<<endl;MChoice();};
}

void Graph::ChangeMWeight() {
    int times;///改动次数
    cout<<"请输入赋权次数"<<endl;
    cin>>times;
    while(times--){
        int a,b,weight;
        cout<<"请分别输入两个顶点以及他们之间的权重，用空格分割，有向图需要考虑顺序"<<endl;
        cin>>a>>b>>weight;
        a--;b--;
        if (a>vertexmax || b>vertexmax ||a<0 ||b<0) {
            cout << "超过范围,请重新输入" << endl;
            times++;
        }
        else{
            array[a][b]->initialized = 1;
            array[a][b]->Weight = weight;
            if(undigraph){
                array[b][a]->initialized = 1;
                array[b][a]->Weight = weight;
            }
            cout<<"本轮完成，还有"<<times<<"次"<<endl;
        }

    }

}

void Graph::listVertexes() {
    int i,j,mtx[vertexmax],count;
    for(i=0;i<vertexmax;i++){mtx[i]=0;}///为了避免重复输出，需要创建一个数组
    cout<<"Vertexes include ";
    for (i = 0; i < vertexmax; i++) {
        for (j = 0; j < vertexmax; j++) {
            if(array[i][j]->initialized) {
                mtx[i]=1;
                mtx[j]=1;
            }
        }
    }
    for(i = 0; i < vertexmax; i++) {
        if (mtx[i]) {cout << i + 1 << ' ';}
    }
    cout<<endl;
}

void Graph::listEdges() {
    int i, j;
    int flag = 1;
    cout<<"Edges include "<<endl;
    for (i = 0; i < vertexmax; i++) {
        for (j = 0; j < vertexmax; j++) {
            if (array[i][j]->initialized != 0) {
                flag = 0;
                printf("(%d, %d, %d)\n", i + 1, j + 1, array[i][j]->Weight);
            }
        }
    }
    if (flag) cout << "No Edges yet..." << endl;
}

///--------邻接表--------

void Graph::CreateLGraph(LGraph &G){
    cout<<"无向图输入1，有向图输入0，"<<endl;
    cin>>undigraph;
    int i;
    cout<<"输入顶点数:"<<endl;
    cin>>G.vexnum;
    if(undigraph){cout<<"建立了一个顶点数为"<<G.vexnum<<"的无向图，使用邻接表存储"<<endl;}
    else{cout<<"建立了一个顶点数为"<<G.vexnum<<"的有向图，使用邻接表存储"<<endl;}
    for(i=0;i<G.vexnum;i++){
        G.Vex[i].data=i+1;
        G.Vex[i].first= nullptr;
    }
}


void Graph::_insertedge(Graph::LGraph &G, int i, int j, int wgt){
    AdjNode *s;
    s=new AdjNode;
    s->v=j;
    s->wgt=wgt;
    s->next=G.Vex[i].first;
    G.Vex[i].first=s;
}
void Graph::listEdges(Graph::LGraph G){
    cout<<"Edges include"<<endl;
    for(int i=0; i<G.vexnum; i++)
    {
        AdjNode* t=G.Vex[i].first;
        _listAdjNode(G.Vex[i].data, t);
    }
}

void Graph::_listAdjNode(int data, Graph::AdjNode *t) {
    printf("(%d, %d, %d)\n",data, t->v+1, t->wgt);
    if(t->next!= nullptr) _listAdjNode(data, t->next);
}

void Graph::listVertexes(Graph::LGraph G) {
    int i;
    cout<<"Vertexes include "<<endl;
    for(i=0; i<G.vexnum; i++){
        cout<<G.Vex[i].data<<' ';
    }
    cout<<endl;
}


#endif // !_CMAP_H_